package com.learn.datastructure.heap;

import jdk.internal.util.ArraysSupport;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Java 实现的堆，模仿{@link PriorityQueue}
 *
 * @see PriorityQueue
 */
public class JavaHeap<E> implements IHeap<E> {

    /**
     * 默认容量
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * 使用数组来存储堆中的元素
     */
    transient Object[] queue;

    /**
     * 堆大小
     */
    int size;

    /**
     * 比较器
     */
    private final Comparator<? super E> comparator;

    /**
     * 修改次数
     */
    transient int modCount;

    // ----------------- 构造 ---------------------------------
    public JavaHeap() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    public JavaHeap(int initialCapacity) {
        this(initialCapacity, null);
    }

    public JavaHeap(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

    public JavaHeap(int initialCapacity,
                    Comparator<? super E> comparator) {
        // Note: This restriction of at least one is not actually needed,
        // but continues for 1.5 compatibility
        if (initialCapacity < 1) {
            throw new IllegalArgumentException();
        }
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }
    // ----------------- 构造 ---------------------------------


    /**
     * 元素入堆
     *
     * @param e 元素
     * @return boolean
     */
    @Override
    public boolean push(E e) {
        // 非法判断
        if (e == null) {
            throw new NullPointerException();
        }
        modCount++;
        int i = size;
        if (i >= queue.length) {
            // 长度增长
            grow(i + 1);
        }
        // 向上筛选
        siftUp(i, e);
        size = i + 1;
        return true;
    }

    /**
     * 向上筛选
     *
     * @param k 下标
     * @param x 元素
     */
    private void siftUp(int k, E x) {
        if (comparator != null) {
            siftUpUsingComparator(k, x, queue, comparator);
        } else {
            siftUpComparable(k, x, queue);
        }
    }

    /**
     * 使用节点自身的编辑器进行比较来向上筛选
     *
     * @param k   游标
     * @param x   比较的元素
     * @param es  数组
     * @param <T>
     */
    private <T> void siftUpComparable(int k, T x, Object[] es) {
        Comparable<? super T> key = (Comparable<? super T>) x;
        while (k > 0) {
            // 获取到父节点下标
            int parent = (k - 1) >>> 1;
            // 父节点元素
            Object e = es[parent];
            // 当前元素 >= 父节点元素，则退出循环
            if (key.compareTo((T) e) >= 0) {
                break;
            }
            // 满足置换条件， 将父节点元素已到当前节点的位置
            es[k] = e;
            // 将遍历的下标改为父节点下标，继续向上遍历
            k = parent;
        }
        es[k] = key;
    }

    /**
     * 使用比较器比较进行向上筛选
     *
     * @param k   游标
     * @param x   比较的元素
     * @param es  数组
     * @param cmp 比较器
     * @param <T>
     */
    private <T> void siftUpUsingComparator(int k, T x, Object[] es, Comparator<? super T> cmp) {
        while (k > 0) {
            // 父节点下标: (k - 1) / 2
            int parent = (k - 1) >>> 1;
            // 父节点元素
            Object e = es[parent];
            // 当前元素 >= 父节点元素，则退出循环
            if (cmp.compare(x, (T) e) >= 0) {
                break;
            }
            // 满足置换条件， 将父节点元素已到当前节点的位置
            es[k] = e;
            // 将遍历的下标改为父节点下标，继续向上遍历
            k = parent;
        }
        es[k] = x;
    }


    /**
     * 堆顶元素出堆
     *
     * @return E
     */
    @Override
    public E pop() {
        // 数组副本
        final Object[] es;
        // 返回结果 - 堆顶元素
        final E result;
        // 对数组副本进行赋值
        // 获取堆顶元素，如果不为空，需要进行数据维护 - 向下筛选
        if ((result = (E) ((es = queue)[0])) != null) {
            modCount++;
            // 出堆之后的数组长度
            final int n;
            // 算出当前的数组长度
            // 将数组的最后一个元素赋值给 x
            final E x = (E) es[(n = --size)];
            es[n] = null;
            if (n > 0) {
                final Comparator<? super E> cmp;
                if ((cmp = comparator) == null) {
                    siftDownComparable(0, x, es, n);
                } else {
                    siftDownUsingComparator(0, x, es, n, cmp);
                }
            }
        }
        return result;
    }

    /**
     * 使用比较器详细筛选
     *
     * @param k
     * @param x
     * @param es
     * @param n
     * @param <T>
     */
    private <T> void siftDownComparable(int k, T x, Object[] es, int n) {
        // assert n > 0;
        Comparable<? super T> key = (Comparable<? super T>) x;
        // 取 0 - n 的中间节点 -> 二分搜索
        int half = n >>> 1;
        while (k < half) {
            // child：当前节点的子节点，当前节点有左右子节点，比较，取大的节点来继续搜索
            // 获取 k 的左边子节点下标 -> (2 * k) + 1
            int child = (k << 1) + 1;
            // 获取左边子节点元素值
            Object c = es[child];
            // 右边子节点下标 -> (2 * k) + 2
            int right = child + 1;
            if (right < n && ((Comparable<? super T>) c).compareTo((T) es[right]) > 0) {
                // 左右子节点取大的 赋值给 c
                c = es[child = right];
            }
            if (key.compareTo((T) c) <= 0) {
                // 如果此时对比元素 x 小于 c，退出循环
                break;
            }

            // 将当前的子节点的元素赋值给当前游标k所处的位置，完成一次替换，准备下一次查询
            es[k] = c;
            // 继续二分搜索逻辑，将当前的子节点下标复制给游标k
            k = child;
        }
        es[k] = key;
    }

    /**
     * 使用元素比较器向下筛选
     *
     * @param k
     * @param x
     * @param es
     * @param n
     * @param cmp
     * @param <T>
     */
    private <T> void siftDownUsingComparator(
            int k, T x, Object[] es, int n, Comparator<? super T> cmp) {
        // assert n > 0;
        int half = n >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = es[child];
            int right = child + 1;
            if (right < n && cmp.compare((T) c, (T) es[right]) > 0) {
                c = es[child = right];
            }
            if (cmp.compare(x, (T) c) <= 0) {
                break;
            }
            es[k] = c;
            k = child;
        }
        es[k] = x;
    }

    /**
     * 访问堆顶元素（大 / 小顶堆分别为最大 / 小值）
     *
     * @return
     */
    @Override
    public E peek() {
        return (E) queue[0];
    }

    /**
     * 获取堆的元素数量
     *
     * @return int
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 判断堆是否为空
     *
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        return size() == 0;
    }


    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = ArraysSupport.newLength(oldCapacity,
                minCapacity - oldCapacity, /* minimum growth */
                oldCapacity < 64 ? oldCapacity + 2 : oldCapacity >> 1
                /* preferred growth */);
        queue = Arrays.copyOf(queue, newCapacity);
    }
}
